/*
题目：第K个最小的素数分数
给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数  组成，且其中所有整数互不相同。

对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。

那么第 k 个最小的分数是多少呢?  以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。
https://leetcode.cn/problems/k-th-smallest-prime-fraction/
 */
public class KthSmallestPrimeFraction {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        //构造容量为 k 的 大根 堆，元素类型为int[] {arr[i], arr[j]}, 0下标元素 / 1下标元素就是相应的小数
        PriorityQueue<int[]> heap = new PriorityQueue<> (new DecimalCmp());
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int[] curr = new int[] {arr[i], arr[j]};
                if (heap.size() < k) {
                    heap.offer(curr);
                } else if (isSmaller(curr, heap.peek())) { //如果下一个元素比堆顶元素小，那就将堆顶元素替换掉
                    heap.poll();
                    heap.offer(curr);
                }
            }
        }

        return heap.peek(); //堆顶元素就是第k小的元素
    }

    private boolean isSmaller(int[] o1, int[] o2) { //比较大小
        return o1[0] * o2[1] - o2[0] * o1[1] < 0;
    }
}

class DecimalCmp implements Comparator<int[]> {
    public int compare(int[] o1, int[] o2) {
        return o2[0] * o1[1] - o1[0] * o2[1];
    }
}
